/**
 * 给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。
 * PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
 * 这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。
 * https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/hui-su-suan-fa-xiang-jie-xiu-ding-ban
 */

 //克隆2维数组
 function cloneArr(arr){
     return arr.map(element => {
         return [...element];
     });
 }

function main(n) {
    var res = [];
    var board = [];
    for (let i = 0; i < n; i++) {
        if (!board[i]) {
            board[i] = [];
        }
        for (let j = 0; j < n; j++) {
            board[i][j] = '.';
        }
    }

    backtrack(board, 0);

    function backtrack(board, row) {
        // 触发结束条件
        if (row === board.length) {
            res.push(cloneArr(board));
            return true;
        }

        var n = board[row].length;

        for (let col = 0; col < n; col++) {
            if (!isValid(board, row, col)) {
                continue;
            }
            board[row][col] = 'Q';// 做选择

            if (backtrack(board, row + 1)) { //进行下一行决策
                // return true; //如果只查一种就返回
            }

            board[row][col] = '.'; //撤销选择
        }
    }
    return res;
}

function isValid(board, row, col) {
    var n = board.length;
    for (let i = 0; i < n; i++) {
        if (board[i][col] === 'Q') {
            return false;
        }
    }

    //检查右上方是否有皇后互相冲突
    for (var i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] === 'Q')
            return false;
    }
    // 检查左上方是否有皇后互相冲突
    for (var i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] === 'Q')
            return false;
    }
    return true;
}

console.log(main(8));